package com.practice.zuocy.base.class02;

import java.util.Stack;

/**
 * 题目：
 * 实现一个特殊的栈，在基础功能的基础上，再实现返回栈中最小元素的功能
 * （1）pop, push, getMin操作的时间复杂度都是O(1)
 * （2）设计的栈类型可以使用现成的栈结构。
 * （TODO 说明：其实就是实现一个栈中最小值的更新结构）
 */
public class Code05_GetMinStack {

	/**
	 * 方法一：实现这个getMin的栈
	 */
	public static class MyStack1 {
		// 1. 准备两个栈
		// 1.1 数据栈
		private Stack<Integer> stackData;
		// 1.2 min栈
		private Stack<Integer> stackMin;

		public MyStack1() {
			this.stackData = new Stack<Integer>();
			this.stackMin = new Stack<Integer>();
		}

		/**
		 * 往这个getMin栈中加入一个数
		 *
		 * @param newNum 待加入的数
		 */
		public void push(int newNum) {
			if (this.stackMin.isEmpty()) {
				this.stackMin.push(newNum);
			} else if (newNum <= this.getmin()) {
				this.stackMin.push(newNum);
			}
			this.stackData.push(newNum);
		}

		/**
		 * 从这个getMin栈中弹出一个数
		 *
		 * @return 弹出的数
		 */
		public int pop() {
			if (this.stackData.isEmpty()) {
				throw new RuntimeException("Your stack is empty.");
			}
			int value = this.stackData.pop();
			if (value == this.getmin()) {
				this.stackMin.pop();
			}
			return value;
		}

		/**
		 * 获取getMin栈中的最小值
		 *
		 * @return 最小值
		 */
		public int getmin() {
			if (this.stackMin.isEmpty()) {
				throw new RuntimeException("Your stack is empty.");
			}
			return this.stackMin.peek();
		}
	}

	/**
	 * 方法二：实现这个getMin的栈
	 */
	public static class MyStack2 {
		// 1. 准备两个栈
		// 1.1 数据栈
		private Stack<Integer> stackData;
		// 1.2 min栈
		private Stack<Integer> stackMin;

		public MyStack2() {
			this.stackData = new Stack<Integer>();
			this.stackMin = new Stack<Integer>();
		}

		/**
		 * 往这个getMin栈中加入一个数
		 *
		 * @param newNum 待加入的数
		 */
		public void push(int newNum) {
			if (this.stackMin.isEmpty()) {
				this.stackMin.push(newNum);
			} else if (newNum < this.getmin()) {
				this.stackMin.push(newNum);
			} else {
				int newMin = this.stackMin.peek();
				this.stackMin.push(newMin);
			}
			this.stackData.push(newNum);
		}

		/**
		 * 从这个getMin栈中弹出一个数
		 *
		 * @return 弹出的数
		 */
		public int pop() {
			if (this.stackData.isEmpty()) {
				throw new RuntimeException("Your stack is empty.");
			}
			this.stackMin.pop();
			return this.stackData.pop();
		}

		/**
		 * 获取getMin栈中的最小值
		 *
		 * @return 最小值
		 */
		public int getmin() {
			if (this.stackMin.isEmpty()) {
				throw new RuntimeException("Your stack is empty.");
			}
			return this.stackMin.peek();
		}
	}

	public static void main(String[] args) {
		MyStack1 stack1 = new MyStack1();
		stack1.push(3);
		System.out.println(stack1.getmin());
		stack1.push(4);
		System.out.println(stack1.getmin());
		stack1.push(1);
		System.out.println(stack1.getmin());
		System.out.println(stack1.pop());
		System.out.println(stack1.getmin());

		System.out.println("=============");

		MyStack1 stack2 = new MyStack1();
		stack2.push(3);
		System.out.println(stack2.getmin());
		stack2.push(4);
		System.out.println(stack2.getmin());
		stack2.push(1);
		System.out.println(stack2.getmin());
		System.out.println(stack2.pop());
		System.out.println(stack2.getmin());
	}

}
